package org.nkumar.stl;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;

/**
 * This class is a java port of C++ STL algorithms. <br>
 * Instead of dealing with iterators, this class deals with java Lists.
 * If one wishes to apply the algorithm to a part of the list then
 * one can use List.sublist(int.int) method to get the sublist backed
 * by the original list. <br>
 * Instead of using method pointers, this class makes use of interfaces,
 * like Predicate, BinaryPredicate and Comparator. <br>
 * Most methods in this class is implemented in two ways, one using iterators
 * and another using index based gets. Iterating through a list using index
 * is faster in lists that implement Random Access interface.
 * See java.util.RandomAccess (JDK1.4) for details.<br>
 * In mutative algorithms that take in two lists, and either of them
 * is not implementing Random access then iterators will be used.
 * In such a scenario one must not pass the same list in both the parameters.
 * This may throw ConcurrentModificationException. <br>
 * This class takes effort not to throw NullPointerException. So in all
 * cases null list is treated the same as empty list. The only exception is the
 * equal method, where null list and empty list are not equal. Even in
 * this method two null lists are considered equal. <br>
 * In mutative algorithms the list on which the mutation will take place
 * should not be null or else IllegalArgumentException is thrown. <br>
 * Similarly when comparing two objects, within a list, for equality, checks for nulls are
 * made, and two nulls are treated equal. Similarly when no Comparator is
 * provided the this class uses NullLowComparator by default.
 * @author Nishant Kumar
 */
@SuppressWarnings({"BooleanMethodNameMustStartWithQuestion", "ObjectEquality"})
public final class ListHelper
{
    private ListHelper()
    {
    }

    /**
     * Returns the index of the first occurrence of value in the list or -1 if no such index exists.
     * Returns -1 if the list is <code>null</code>.
     * Value passed can be <code>null</code> in which case the index of the first occurrence
     * of <code>null</code> is returned.
     * @param list list
     * @param value the object to be searched
     * @return the index of the first occurrence of value in the list or -1 if no such index exists.
     */
    public static <T> int find(final List<? super T> list, final T value)
    {
        return findIf(list, new ObjectPredicate(value));
    }

    /**
     * Returns the first index in list such that the object at this index satifies the predicate
     * or -1 if no such index exists.
     * Returns -1 if the list is <code>null</code>.
     * @param list list
     * @param predicate the condition that has to be met.
     * @return the first index in list such that the object at this index
     *         satifies the predicate or -1 if no such index exists.
     * @throws IllegalArgumentException if predicate passed is null
     */
    public static <T> int findIf(final List<T> list, final Predicate<? super T> predicate)
    {
        if (list == null)
        {
            return -1;
        }
        if (predicate == null)
        {
            throw new IllegalArgumentException("Predicate was null");
        }

        if (list instanceof RandomAccess)
        {
            final int size = list.size();
            for (int i = 0; i < size; i++)
            {
                if (predicate.test(list.get(i)))
                {
                    return i;
                }
            }
        }
        else
        {
            final ListIterator<T> lit = list.listIterator();
            while (lit.hasNext())
            {
                if (predicate.test(lit.next()))
                {
                    return lit.previousIndex();
                }
            }
        }
        return -1;
    }

    /**
     * Returns the first index i such that i and i+1 are both within the list, and
     * objects are equal at these indexes. Returns -1 if no such index exists or
     * if the list is <code>null</code>.
     * Comparison is null safe. Two nulls are treated as equal.
     * @param list list
     * @return the first index i such that i and i+1 are both within the list, and
     *         objects are equal at these indexes.
     */
    public static <T> int adjacentFind(final List<T> list)
    {
        return adjacentFind(list, EQ_BIN_PRED);
    }

    /**
     * Returns the first index i such that i and i+1 are both within the list, and
     * objects at these indexes satisfy the binaryPredicate.
     * Returns -1 if no such index exists or if the list is <code>null</code>.
     * @param list list
     * @param binaryPredicate the condition that the two objects have to satisfy
     * @return the first index i such that i and i+1 are both within the list, and
     *         objects at these indexes satisfy the binaryPredicate.
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T> int adjacentFind(final List<T> list, final BinaryPredicate<? super T> binaryPredicate)
    {
        if (list == null)
        {
            return -1;
        }
        if (binaryPredicate == null)
        {
            throw new IllegalArgumentException("BinaryPredicate was null");
        }

        if (list instanceof RandomAccess)
        {
            final int size = list.size();
            if (size < 2)
            {
                return -1;
            }
            T first = list.get(0);
            for (int i = 1; i < size; i++)
            {
                final T second = list.get(i);
                if (binaryPredicate.test(first, second))
                {
                    return i - 1;
                }
                first = second;
            }
        }
        else
        {
            final ListIterator<T> lit = list.listIterator();
            if (!lit.hasNext())
            {
                return -1;
            }
            T first = lit.next();
            while (lit.hasNext())
            {
                final T second = lit.next();
                if (binaryPredicate.test(first, second))
                {
                    return lit.previousIndex() - 1;
                }
                first = second;
            }
        }
        return -1;
    }

    /**
     * Returns the first occurrance in the first list of any of the elements
     * in the second list.
     * Uses the normal equals method to compare. Returns -1 if no such index exists
     * or either of the lists is <code>null</code>.
     * Comparison is null safe. Two nulls are treated as equal.
     * @param list1 the first list
     * @param list2 the second list
     * @return the first occurrance in the first list of any of the elements
     *         in the second list.
     */
    public static <T> int findFirstOf(final List<T> list1, final List<? extends T> list2)
    {
        return findFirstOf(list1, list2, EQ_BIN_PRED);
    }

    /**
     * Returns the first occurrance of an element in the first list
     * such that this element and any one of the elements of the second list
     * satisfy the BinaryPredicate.
     * Returns -1 if no such index exists
     * or either of the lists is <code>null</code>.
     * @param list1 the first list
     * @param list2 the second list
     * @param binaryPredicate the condition that the two objects have to satisfy
     * @return the first occurrance of an element in the first list
     *         such that this element and any one of the elements of the second list
     *         satisfy the BinaryPredicate.
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T> int findFirstOf(final List<T> list1, final List<? extends T> list2,
            final BinaryPredicate<? super T> binaryPredicate)
    {
        if (list1 == null || list2 == null || list1.isEmpty() || list2.isEmpty())
        {
            return -1;
        }
        if (binaryPredicate == null)
        {
            throw new IllegalArgumentException("BinaryPredicate was null");
        }

        if (list1 instanceof RandomAccess && list2 instanceof RandomAccess)
        {
            final int size1 = list1.size();
            final int size2 = list2.size();
            for (int i = 0; i < size1; i++)
            {
                final T val = list1.get(i);
                for (int j = 0; j < size2; j++)
                {
                    if (binaryPredicate.test(val, list2.get(j)))
                    {
                        return i;
                    }
                }
            }
        }
        else
        {
            final ListIterator<T> lit1 = list1.listIterator();
            while (lit1.hasNext())
            {
                final T val = lit1.next();
                final ListIterator<? extends T> lit2 = list2.listIterator();
                while (lit2.hasNext())
                {
                    if (binaryPredicate.test(val, lit2.next()))
                    {
                        return lit1.previousIndex();
                    }
                }
            }
        }
        return -1;
    }

    /**
     * Returns the number of elements within the list that are equal to
     * the given value. Returns 0 if the list is <code>null</code>.
     * @param list list
     * @param value the object to be counted. this may be <code>null</code>,
     * in which case the number of <code>null</code>s in the list is returned.
     * @return the number of elements within the list that are equal to value.
     */
    public static <T> int count(final List<? super T> list, final T value)
    {
        return countIf(list, new ObjectPredicate(value));
    }

    /**
     * Returns the number of elements in the list that satisfy the predicate.
     * Returns 0 if the list is <code>null</code>.
     * @param list list
     * @param predicate the codition to be satisfied
     * @return the number of elements in the list that satisfy the predicate.
     * @throws IllegalArgumentException if passed predicate is null
     */
    public static <T> int countIf(final List<T> list, final Predicate<? super T> predicate)
    {
        if (list == null)
        {
            return 0;
        }
        if (predicate == null)
        {
            throw new IllegalArgumentException("Predicate was null");
        }

        int count = 0;
        if (list instanceof RandomAccess)
        {
            final int size = list.size();
            for (int i = 0; i < size; i++)
            {
                if (predicate.test(list.get(i)))
                {
                    ++count;
                }
            }
        }
        else
        {
            for (final T element : list)
            {
                if (predicate.test(element))
                {
                    ++count;
                }
            }
        }
        return count;
    }

    /**
     * Returns the first position where the two lists differ when compared element
     * by element ie the objects at that index are unequal in the two lists.
     * Comparison is null safe. Two nulls are treated as equal.
     * If the two lists differ in size but their contents are the same till the
     * end of the smaller list then the size of the smaller list is returned.
     * Returns -1 if the lists are equal, ie of same size and having equal
     * elements in the same sequence.
     * <code>null</code> lists are considered same as empty lists.
     * Returns -1 if both the lists are <code>null</code>.
     * Returns 0 if just one of the lists is <code>null</code> and the other has some content.
     * @param list1 the first list
     * @param list2 the second list
     * @return the first position in the first list where the two lists differ.
     */
    public static <T> int mismatch(final List<T> list1, final List<T> list2)
    {
        return mismatch(list1, list2, EQ_BIN_PRED);
    }

    /**
     * Returns the first position where the objects in the two lists donot satisfy
     * the binaryPredicate. If the two lists differ in size but their contents
     * satisfy the binaryPredicate, element by element, till the end of the
     * smaller list then the size of the smaller list is returned.
     * Returns -1 if the lists are equal, ie of same size and elements that
     * satisfy the binaryPredicate.
     * <code>null</code> lists are considered same as empty lists.
     * Returns -1 if both the lists are <code>null</code>.
     * Returns 0 if just one of the lists is <code>null</code> and the other has some content.
     * @param list1 the first list
     * @param list2 the second list
     * @param binaryPredicate the condition to be met
     * @return the first position where the objects in the two lists donot satisfy
     *         the binaryPredicate.
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T> int mismatch(final List<T> list1, final List<T> list2,
            final BinaryPredicate<? super T> binaryPredicate)
    {
        if (list1 == null && list2 == null)
        {
            return -1;
        }
        if (list1 == null)
        {
            return (list2.isEmpty()) ? -1 : 0;
        }
        if (list2 == null)
        {
            return (list1.isEmpty()) ? -1 : 0;
        }
        if (binaryPredicate == null)
        {
            throw new IllegalArgumentException("BinaryPredicate was null");
        }

        if (list1 instanceof RandomAccess && list2 instanceof RandomAccess)
        {
            final int size1 = list1.size();
            final int size2 = list2.size();
            for (int i = 0; i < size1; i++)
            {
                if (i == size2)
                {
                    return i;
                }
                if (!binaryPredicate.test(list1.get(i), list2.get(i)))
                {
                    return i;
                }
            }
            if (size1 < size2)
            {
                return size1;
            }
        }
        else
        {
            final ListIterator<T> lit1 = list1.listIterator();
            final ListIterator<T> lit2 = list2.listIterator();
            while (lit1.hasNext())
            {
                if (!lit2.hasNext())
                {
                    return lit1.nextIndex();
                }
                if (!binaryPredicate.test(lit1.next(), lit2.next()))
                {
                    return lit1.previousIndex();
                }
            }
            if (lit2.hasNext())
            {
                return lit1.nextIndex();
            }
        }
        return -1;
    }

    /**
     * Returns <code>true</code> if the two lists are identical when compared
     * element-by-element, otherwise returns <code>false</code>.
     * Similar to java.util.List.equals() but this method can compare
     * <code>null</code> lists too.
     * In this case a <code>null</code> list and an empty list differ.
     * @param list1 the first list
     * @param list2 the second list
     * @return returns <code>true</code> if the two lists
     *         are identical when compared element-by-element, and otherwise returns false.
     */
    public static <T> boolean equal(final List<T> list1, final List<T> list2)
    {
        return equal(list1, list2, EQ_BIN_PRED);
    }

    /**
     * Returns <code>true</code> when the corresponding elements of the two
     * lists satisfy the binaryPredicate, <code>false</code> otherwise.
     * In this case a <code>null</code> list and an empty list differ.
     * @param list1 the first list
     * @param list2 the second list
     * @param binaryPredicate the condition to be met
     * @return <code>true</code> when the corresponding elements of the two
     *         lists satisfy the binaryPredicate, <code>false</code> otherwise.
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T> boolean equal(final List<T> list1, final List<T> list2,
            final BinaryPredicate<? super T> binaryPredicate)
    {
        if (list1 == null && list2 == null)
        {
            return true;
        }
        if (list1 == null || list2 == null)
        {
            return false;
        }
        return (list1.size() == list2.size()) && (mismatch(list1, list2, binaryPredicate) == -1);
    }

    /**
     * Returns the index pointing to the beginning of the subsequence within the
     * first list that is identical to the second list when compared element-by-element.
     * Returns -1 if no such subsequence exists or either of the lists is
     * <code>null</code> or empty.
     * @param list1 the first list
     * @param list2 the second list
     * @return Returns the index pointing to the beginning of the subsequence
     *         within the first list that is identical to the second list when compared
     *         element-by-element.
     */
    public static <T> int search(final List<T> list1, final List<? extends T> list2)
    {
        return search(list1, list2, EQ_BIN_PRED);
    }

    /**
     * Returns the index pointing to the beginning of the subsequence within the
     * first list such that the corresponding elements of the subsequence and
     * the second list satisfy the binaryPredicate.
     * Returns -1 if no such subsequence exists or either of the lists is
     * <code>null</code> or empty.
     * @param list1 the first list
     * @param list2 the second list
     * @param binaryPredicate the condition to be met
     * @return Returns the index pointing to the beginning of the subsequence
     *         within the first list such that the corresponding elements of the
     *         subsequence and the second list satisfy the binaryPredicate.
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T, S extends T> int search(final List<T> list1, final List<S> list2,
            final BinaryPredicate<? super T> binaryPredicate)
    {
        if (list1 == null || list2 == null)
        {
            return -1;
        }
        if (binaryPredicate == null)
        {
            throw new IllegalArgumentException("BinaryPredicate was null");
        }

        final int size1 = list1.size();
        final int size2 = list2.size();
        if (size1 == 0 || size2 == 0 || size1 < size2)
        {
            return -1;
        }

        //Test for a pattern of length 1
        if (size2 == 1)
        {
            final S firstlist2 = list2.get(0);
            if (list1 instanceof RandomAccess)
            {
                for (int i = 0; i < size1; i++)
                {
                    if (binaryPredicate.test(list1.get(i), firstlist2))
                    {
                        return i;
                    }
                }
            }
            else
            {
                final ListIterator<T> lit1 = list1.listIterator();
                while (lit1.hasNext())
                {
                    if (binaryPredicate.test(lit1.next(), firstlist2))
                    {
                        return lit1.previousIndex();
                    }
                }
            }
            return -1;
        }

        //General Case
        if (list1 instanceof RandomAccess && list2 instanceof RandomAccess)
        {
            int index = 0;
            final S firstlist2 = list2.get(0);
            while ((size1 - index) >= size2)
            {
                //get to the possible start of the subsequence by comparing the first element of list2
                while ((size1 - index) >= size2)
                {
                    if (binaryPredicate.test(list1.get(index++), firstlist2))
                    {
                        break;
                    }
                }

                if ((size1 - index) < (size2 - 1))
                {
                    return -1;
                }

                //store the possible start index
                final int start = index - 1;

                //check whether the rest of the subsequence matches the rest of the second list.
                int index2 = 1;
                while (binaryPredicate.test(list1.get(index++), list2.get(index2++)))
                {
                    if (index2 == size2)
                    {
                        return start;
                    }
                }
                index = start + 1;
            }
        }
        else
        {
            int index = 0;                         //represents lit1.nextIndex();
            while ((size1 - index) >= size2)
            {
                final ListIterator<T> lit1 = list1.listIterator(index);
                final ListIterator<S> lit2 = list2.listIterator();
                final S firstlist2 = lit2.next();

                //get to the possible start of the subsequence by comparing the first element of list2
                while ((size1 - index) >= size2)
                {
                    index++;
                    if (binaryPredicate.test(lit1.next(), firstlist2))
                    {
                        break;
                    }
                }

                if ((size1 - index) < (size2 - 1))
                {
                    return -1;
                }

                //store the possible start index
                final int start = index - 1;

                //check whether the rest of the subsequence matches the rest of the second list.
                while (binaryPredicate.test(lit1.next(), lit2.next()))
                {
                    if (!lit2.hasNext())
                    {
                        return start;
                    }
                }
            }
        }
        return -1;
    }


    /**
     * Returns an index pointing to the beginning of a subsequence of count
     * consecutive elements in the list, all of which are equal to value.
     * Returns -1 if no such subsequence exists or the count is less than or
     * equal to zero or the list is <code>null</code>.
     * @param list list
     * @param count the length of the subsequence to be found
     * @param value the object whose count consecutive occurence has to be found.
     * @return Returns an index pointing to the beginning of a subsequence of
     *         count consecutive elements in the list, all of which are equal to value.
     */
    public static <T> int searchN(final List<? super T> list, final int count, final T value)
    {
        return searchN(list, count, value, EQ_BIN_PRED);
    }

    /**
     * Returns an index pointing to the beginning of a subsequence of count
     * consecutive elements in the list, such that each element in the subsequence
     * and the value object satisfy the binarypredicate.
     * Returns -1 if no such subsequence exists or the count is less than or equal
     * to zero or the list is <code>null</code>.
     * @param list list
     * @param count the length of the subsequence to be found
     * @param value the object whose count consecutive occurence has to be found.
     * @param binaryPredicate the condition to be met
     * @return Returns an index pointing to the beginning of a subsequence of
     *         count consecutive elements in the list, such that each element in the
     *         subsequence and the value object satsfy the binarypredicate.
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T, S extends T> int searchN(final List<T> list, final int count,
            final S value, final BinaryPredicate<? super T> binaryPredicate)
    {
        if (list == null || count <= 0)
        {
            return -1;
        }
        if (binaryPredicate == null)
        {
            throw new IllegalArgumentException("BinaryPredicate was null");
        }

        final int size = list.size();
        if (size < count)
        {
            return -1;
        }

        if (count == 1)
        {
            if (list instanceof RandomAccess)
            {
                for (int i = 0; i < size; i++)
                {
                    if (binaryPredicate.test(list.get(i), value))
                    {
                        return i;
                    }
                }
            }
            else
            {
                final ListIterator<T> itr = list.listIterator();
                while (itr.hasNext())
                {
                    if (binaryPredicate.test(itr.next(), value))
                    {
                        return itr.previousIndex();
                    }
                }
            }
            return -1;
        }
        else
        {
            if (list instanceof RandomAccess)
            {
                int index = 0;
                while (index < size)
                {
                    //get the index of the first element of the possible subsequence
                    boolean firstFound = false;
                    while ((size - index) >= count)
                    {
                        if (binaryPredicate.test(list.get(index++), value))
                        {
                            firstFound = true;
                            break;
                        }
                    }
                    if (!firstFound)
                    {
                        return -1;
                    }

                    final int start = index - 1;

                    //compare the rest of the sunsequence and the second list
                    int index2 = 1;
                    while (binaryPredicate.test(list.get(index++), value))
                    {
                        ++index2;
                        if (index2 == count)
                        {
                            return start;
                        }
                    }
                }
            }
            else
            {
                int index = 0;
                final ListIterator<T> lit = list.listIterator();
                while (lit.hasNext())
                {
                    //get the index of the first element of the possible subsequence
                    boolean firstFound = false;
                    while ((size - index) >= count)
                    {
                        index++;
                        if (binaryPredicate.test(lit.next(), value))
                        {
                            firstFound = true;
                            break;
                        }
                    }
                    if (!firstFound)
                    {
                        return -1;
                    }

                    final int start = index - 1;

                    //compare the rest of the sunsequence and the second list
                    int index2 = 1;
                    while (binaryPredicate.test(lit.next(), value))
                    {
                        ++index2;
                        if (index2 == count)
                        {
                            return start;
                        }
                    }
                    index = lit.nextIndex();
                }
            }
            return -1;
        }
    }

    /**
     * Returns the index pointing to the beginning of the last subsequence within the
     * first list that is identical to the second list when compared element-by-element.
     * Returns -1 if no such subsequence exists or either of the lists is
     * <code>null</code> or empty.
     * @param list1 the first list
     * @param list2 the second list
     * @return Returns the index pointing to the beginning of the last subsequence
     *         within the first list that is identical to the second list when compared
     *         element-by-element.
     */
    public static <T> int findEnd(final List<T> list1, final List<? extends T> list2)
    {
        return findEnd(list1, list2, EQ_BIN_PRED);
    }

    /**
     * Returns the index pointing to the beginning of the last subsequence within
     * the first list such that the corresponding elements of the subsequence
     * and the second list satisfy the binaryPredicate.
     * Returns -1 if no such subsequence exists or either of the lists is
     * <code>null</code> or empty.
     * @param list1 the first list
     * @param list2 the second list
     * @param binaryPredicate the condition to be met
     * @return Returns the index pointing to the beginning of the last subsequence
     *         within the first list such that the corresponding elements of the subsequence
     *         and the second list satisfy the binaryPredicate.
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T, S extends T> int findEnd(final List<T> list1, final List<S> list2,
            final BinaryPredicate<? super T> binaryPredicate)
    {
        if (list1 == null || list2 == null)
        {
            return -1;
        }
        final int size1 = list1.size();
        if (size1 == 0)
        {
            return -1;
        }
        final int size2 = list2.size();
        if (size2 == 0 || size1 < size2)
        {
            return -1;
        }
        if (binaryPredicate == null)
        {
            throw new IllegalArgumentException("BinaryPredicate was null");
        }

        //Test for a pattern of length 1
        if (size2 == 1)
        {
            final S list2lastObject = list2.get(0);
            if (list1 instanceof RandomAccess)
            {
                for (int i = size1 - 1; i >= 0; i--)
                {
                    if (binaryPredicate.test(list1.get(i), list2lastObject))
                    {
                        return i;
                    }
                }
            }
            else
            {
                final ListIterator<T> lit1 = list1.listIterator(list1.size());
                while (lit1.hasPrevious())
                {
                    if (binaryPredicate.test(lit1.previous(), list2lastObject))
                    {
                        return lit1.nextIndex();
                    }
                }
            }
            return -1;
        }

        //General Case
        if (list1 instanceof RandomAccess && list2 instanceof RandomAccess)
        {
            int index = size1;    //index represents the lit.nextIndex();
            final S list2lastObject = list2.get(size2 - 1);
            while (index >= size2)
            {
                boolean lastFound = false;
                while (index >= size2)
                {
                    if (binaryPredicate.test(list1.get(--index), list2lastObject))
                    {
                        lastFound = true;
                        break;
                    }
                }
                if (!lastFound)
                {
                    return -1;
                }
                //found one get n=size2-1 more
                int i = 1;
                final int n = size2 - 1;
                while (binaryPredicate.test(list1.get(index - i), list2.get(n - i)))
                {
                    i++;
                    if (i == size2)
                    {
                        return index - n;
                    }
                }
            }
        }
        else
        {
            int index = size1;    //index represents the lit.nextIndex();
            while (index >= size2)
            {
                final ListIterator<T> lit1 = list1.listIterator(index);
                final ListIterator<S> lit2 = list2.listIterator(size2);
                final S list2lastObject = lit2.previous();
                boolean lastFound = false;
                while (index >= size2)
                {
                    index--;
                    if (binaryPredicate.test(lit1.previous(), list2lastObject))
                    {
                        lastFound = true;
                        break;
                    }
                }
                if (!lastFound)
                {
                    return -1;
                }
                //found one get n=size2-1 more
                while (binaryPredicate.test(lit1.previous(), lit2.previous()))
                {
                    if (!lit2.hasPrevious())
                    {
                        return lit1.nextIndex();
                    }
                }
            }
        }
        return -1;
    }

    /**
     * Removes all but the first element of a consecutive group of duplicate
     * elements appearing in the list.
     * Returns <code>true</code> if the list has changed.
     * This operation is stable, meaning that the relative order of elements
     * that are not removed is unchanged.
     * @param list list
     * @return <code>true</code> if the list has changed.
     */
    public static <T> boolean unique(final List<T> list)
    {
        return unique(list, EQ_BIN_PRED);
    }

    /**
     * Removes all but the first element of a consecutive group of elements
     * appearing in the list that satisfy the binaryPredicate.
     * Returns <code>true</code> if the list has changed.
     * This operation is stable, meaning that the relative order of elements
     * that are not removed is unchanged.
     * @param list list
     * @param binaryPredicate the condition to be met
     * @return <code>true</code> if the list has changed.
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T> boolean unique(final List<T> list, final BinaryPredicate<? super T> binaryPredicate)
    {
        final int start = adjacentFind(list, binaryPredicate);
        if (start == -1)
        {
            return false;
        }
        final ListIterator<T> lit = list.listIterator(start);
        T value = lit.next();
        lit.next();
        lit.remove();
        T next;
        while (lit.hasNext())
        {
            next = lit.next();
            if (binaryPredicate.test(value, next))
            {
                lit.remove();
            }
            else
            {
                value = next;
            }
        }
        return true;
    }

    /**
     * Removes from the list all elements that are equal to value.
     * Returns <code>true</code> if the list has changed.
     * This operation is stable, meaning that the relative order of elements
     * that are not equal to value is unchanged.
     * @param list list
     * @param value the object to be removed. this can be <code>null</code>
     * in which case all the <code>null</code>s will be removed from the list
     * @return <code>true</code> if the list has changed.
     */
    public static <T> boolean remove(final List<? super T> list, final T value)
    {
        return removeIf(list, new ObjectPredicate(value));
    }

    /**
     * Removes from the list all elements that satisfies the predicate.
     * Returns <code>true</code> if the list has changed.
     * This operation is stable, meaning that the relative order of elements
     * that donot satisfy the predicate is unchanged.
     * @param list list
     * @param predicate the condition to be met
     * @return <code>true</code> if the list has changed.
     * @throws IllegalArgumentException if passed predicate is null
     */
    public static <T> boolean removeIf(final List<T> list, final Predicate<? super T> predicate)
    {
        if (list == null)
        {
            return false;
        }
        if (predicate == null)
        {
            throw new IllegalArgumentException("Predicate was null");
        }

        boolean retVal = false;
        final ListIterator<T> lit = list.listIterator();
        while (lit.hasNext())
        {
            if (predicate.test(lit.next()))
            {
                lit.remove();
                retVal = true;
            }
        }
        return retVal;
    }

    /**
     * Replaces every element in the list equal to oldValue with newValue.
     * Returns <code>true</code> if any replacement takes place. This remains
     * valid even if oldValue and newValue are identical.
     * @param list list
     * @param oldValue the value to be replaced. This can be <code>null</code>
     * in which case <code>null</code>s in the list will be replaced by newValue.
     * @param newValue the value to be replaced with
     * @return <code>true</code> if any replacement takes place.
     */
    public static <T, R extends T, S extends T> boolean replace(final List<T> list,
            final R oldValue, final S newValue)
    {
        if (list == null)
        {
            return false;
        }
        if (oldValue == newValue)
        {
            return (list.indexOf(oldValue) != -1);
        }
        return replaceIf(list, new ObjectPredicate(oldValue), newValue);
    }

    /**
     * Replaces every element in the list which satisfies the predicate with newValue.
     * Returns <code>true</code> if any replacement takes place.
     * @param list list
     * @param predicate the condition to be met
     * @param newValue the value to be replaced with
     * @return <code>true</code> if any replacement takes place.
     * @throws IllegalArgumentException if passed predicate is null
     */
    public static <T, S extends T> boolean replaceIf(final List<T> list,
            final Predicate<? super T> predicate, final S newValue)
    {
        if (list == null)
        {
            return false;
        }
        if (predicate == null)
        {
            throw new IllegalArgumentException("Predicate was null");
        }

        boolean retVal = false;
        if (list instanceof RandomAccess)
        {
            final int size = list.size();
            for (int i = 0; i < size; i++)
            {
                if (predicate.test(list.get(i)))
                {
                    list.set(i, newValue);
                    retVal = true;
                }
            }
        }
        else
        {
            final ListIterator<T> lit = list.listIterator();
            while (lit.hasNext())
            {
                if (predicate.test(lit.next()))
                {
                    lit.set(newValue);
                    retVal = true;
                }
            }
        }
        return retVal;
    }

    /**
     * Returns <code>true</code> if the list is sorted in ascending order.
     * The content of this list must implement java.util.Comparable interface.
     * Empty list and <code>null</code> list are considered sorted.
     * @param list list
     * @return <code>true</code> if the list is sorted in ascending order.
     */
    public static <T extends Comparable<? super T>> boolean isSorted(final List<T> list)
    {
        //TODO fix this
        return isSorted(list, EQ_COMP);
    }

    /**
     * Returns <code>true</code> if the list checked agianst this comparator is
     * found sorted in ascending order.
     * Empty list and <code>null</code> list are considered sorted.
     * @param list list
     * @param comparator the comparator that the defines the order.
     * @return <code>true</code> if the list checked agianst this comparator is
     *         found sorted in ascending order.
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> boolean isSorted(final List<T> list, final Comparator<? super T> comparator)
    {
        if (list == null)
        {
            return true;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }

        if (list instanceof RandomAccess)
        {
            final int size = list.size();
            if (size < 2)
            {
                return true;
            }
            T next;
            int index = 0;
            for (T start = list.get(index++); index < size; start = next)
            {
                next = list.get(index++);
                if (comparator.compare(next, start) < 0)
                {
                    return false;
                }
            }
        }
        else
        {
            final ListIterator<T> lit = list.listIterator();
            if (!lit.hasNext())
            {
                return true;
            }
            T next;
            for (T start = lit.next(); lit.hasNext(); start = next)
            {
                next = lit.next();
                if (comparator.compare(next, start) < 0)
                {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Returns <code>true</code> when the sorted list, list1, includes another sorted list, list2.
     * That is, it returns <code>true</code> if for every element in the second list,
     * there is an equivalent element in the first list.
     * If an element occurrs n time in the second list
     * then an equivalent element should exist in the first list
     * atleast n number of times for this method to return <code>true</code>.
     * Both the lists must be sorted in ascending order.
     * The contents of the two lists must implement java.util.Comparable interface.
     * A <code>null</code> list is treated as an empty list and the above logic is applied.
     * This is different from java.util.List.containsAll() method as this one works on sorted lists.
     * The java.util.List.containsAll() method uses java.lang.Object.equals() method
     * whereas this method uses java.util.Comparable.compareTo() method for comparison.
     * @param list1 the first list
     * @param list2 the second list
     * @return Returns <code>true</code> when the sorted list, list1, includes
     *         another sorted list, list2.
     */
    public static <T extends Comparable<? super T>> boolean includes(final List<T> list1,
            final List<? extends T> list2)
    {
        //TODO fix this
        return includes(list1, list2, EQ_COMP);
    }

    /**
     * Returns <code>true</code> when the sorted list, list1, includes another sorted list, list2.
     * That is, it returns <code>true</code> if for every element in the second list,
     * there is an element in the first list such that the two elements are equal,
     * equality condition governed by the comparator.
     * If an element occurrs n time in the second list
     * then an equivalent element should exist in the first list
     * atleast n number of times for this method to return <code>true</code>.
     * Both the lists must be sorted in ascending order.
     * A <code>null</code> list is treated as an empty list and the above logic is applied.
     * @param list1 the first list
     * @param list2 the second list
     * @param comparator the comparator that the defines the equality condition.
     * @return Returns <code>true</code> when the sorted list, list1, includes
     *         another sorted list, list2.
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T, S extends T> boolean includes(final List<T> list1, final List<S> list2,
            final Comparator<? super T> comparator)
    {
        if (list2 == null || list2.isEmpty())
        {
            return true;
        }
        if (list1 == null || list1.isEmpty())
        {
            return false;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }

        if (list1 instanceof RandomAccess && list2 instanceof RandomAccess)
        {
            final int size1 = list1.size();
            final int size2 = list2.size();
            int index1 = 0;
            int index2 = 0;
            int compareValue;
            T obj1 = list1.get(index1);
            S obj2 = list2.get(index2);
            while (true)
            {
                compareValue = comparator.compare(obj1, obj2);
                if (compareValue > 0)
                {
                    return false;
                }
                else if (compareValue == 0)
                {
                    if (index1 < (size1 - 1) && index2 < (size2 - 1))
                    {
                        obj1 = list1.get(++index1);
                        obj2 = list2.get(++index2);
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    while (compareValue < 0 && index1 < (size1 - 1))
                    {
                        obj1 = list1.get(++index1);
                        compareValue = comparator.compare(obj1, obj2);
                    }
                    if (index1 == size1)
                    {
                        break;
                    }
                }
            }
            return index2 < size2;
        }
        else
        {
            final ListIterator<T> lit1 = list1.listIterator();
            final ListIterator<S> lit2 = list2.listIterator();
            T obj1 = lit1.next();
            S obj2 = lit2.next();
            int compareValue;
            while (true)
            {
                compareValue = comparator.compare(obj1, obj2);
                if (compareValue > 0)
                {
                    return false;
                }
                else if (compareValue == 0)
                {
                    if ((lit1.hasNext() && lit2.hasNext()))
                    {
                        obj1 = lit1.next();
                        obj2 = lit2.next();
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    while (compareValue < 0 && lit1.hasNext())
                    {
                        obj1 = lit1.next();
                        compareValue = comparator.compare(obj1, obj2);
                    }
                    if (!lit1.hasNext())
                    {
                        break;
                    }
                }
            }
            return lit2.hasNext();
        }
    }

    /**
     * Stores the union of the two sorted lists, list1 and list2, in list1.
     * The resulting list is also sorted. Returns <code>true</code> if list1 is changed.
     * In the simplest case, setUnion performs the "union" operation from set theory:
     * the final list1 contains a copy of every element that is contained in list1 , list2, or both.
     * The general case is more complicated, because the input lists may contain duplicate elements.
     * The generalization is that if a value appears m times in list1 and n times
     * in list2 (where m or n may be zero), then it appears max(m,n) times in final list1.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list.
     * @param list2 the second list.
     * @return <code>true</code> if list1 changes.
     */
    public static <T extends Comparable<? super T>> boolean setUnion(final List<T> list1,
            final List<T> list2)
    {
        //TODO fix this
        return setUnion(list1, list2, EQ_COMP);
    }

    /**
     * Stores the union of the two sorted lists, list1 and list2, in list1
     * using the comparator to compare values. The resulting list is also sorted.
     * Returns <code>true</code> if list1 is changed.
     * In the simplest case, setUnion performs the "union" operation from set theory:
     * the final list1 contains a copy of every element that is contained in list1 , list2, or both.
     * The general case is more complicated, because the input lists may contain duplicate elements.
     * The generalization is that if a value appears m times in list1 and n times in
     * list2 (where m or n may be zero), then it appears max(m,n) times in final list1.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list.
     * @param list2 the second list.
     * @param comparator object specifying the comparison logic.
     * @return <code>true</code> if list1 changes.
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> boolean setUnion(final List<T> list1, final List<T> list2,
            final Comparator<? super T> comparator)
    {
        if (list2 == null || list2.isEmpty())
        {
            return false;
        }
        if (list1 == null)
        {
            throw new IllegalArgumentException("first list parameter was null");
        }
        if (list1.isEmpty())
        {
            list1.addAll(list2);
            return true;
        }
        if (list1 == list2)
        {
            return false;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }

        boolean changed = false;
        final ListIterator<T> lit1 = list1.listIterator();
        final ListIterator<T> lit2 = list2.listIterator();
        T obj1 = lit1.next();
        T obj2 = lit2.next();
        while (true)
        {
            final int compareValue = comparator.compare(obj1, obj2);
            if (compareValue < 0)
            {
                if (lit1.hasNext())
                {
                    obj1 = lit1.next();
                }
                else
                {
                    lit1.add(obj2);
                    changed = true;
                    break;
                }
            }
            else if (compareValue > 0)
            {
                lit1.previous();
                lit1.add(obj2);
                lit1.next();
                changed = true;
                if (lit2.hasNext())
                {
                    obj2 = lit2.next();
                }
                else
                {
                    break;
                }
            }
            else
            {
                if ((lit1.hasNext() && lit2.hasNext()))
                {
                    obj1 = lit1.next();
                    obj2 = lit2.next();
                }
                else
                {
                    break;
                }
            }
        }
        while (lit2.hasNext())    //true implies that list1 has ended
        {
            lit1.add(lit2.next());
            changed = true;
        }
        return changed;
    }

    /**
     * Stores the intersection of the two sorted lists, list1 and list2, in list1.
     * The resulting list is also sorted. Returns <code>true</code> if list1 is changed.
     * In the simplest case, setIntersection performs the "intersection" operation from set theory:
     * the final list1 contains a copy of every element that is contained in both list1 and list2.
     * The general case is more complicated, because the input lists may contain duplicate elements.
     * The generalization is that if a value appears m times in list1 and n times in
     * list2 (where m or n may be zero), then it appears min(m,n) times in final list1.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list.
     * @param list2 the second list.
     * @return <code>true</code> if list1 changes.
     */
    public static <T extends Comparable<? super T>> boolean setIntersection(final List<T> list1,
            final List<T> list2)
    {
        //TODO fix this
        return setIntersection(list1, list2, EQ_COMP);
    }

    /**
     * Stores the intersection of the two sorted lists, list1 and list2, in list1
     * using the comparator to compare values. The resulting list is also sorted.
     * Returns <code>true</code> if list1 is changed.
     * In the simplest case, setIntersection performs the "intersection" operation from set theory:
     * the final list1 contains a copy of every element that is contained in both list1 and list2.
     * The general case is more complicated, because the input lists may contain duplicate elements.
     * The generalization is that if a value appears m times in list1 and n times in
     * list2 (where m or n may be zero), then it appears min(m,n) times in final list1.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list.
     * @param list2 the second list.
     * @param comparator object specifying the comparison logic.
     * @return <code>true</code> if list1 changes.
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> boolean setIntersection(final List<T> list1, final List<T> list2,
            final Comparator<? super T> comparator)
    {
        if (list2 == null || list2.isEmpty())
        {
            if (list1 == null || list1.isEmpty())
            {
                return false;
            }
            else
            {
                list1.clear();
                return true;
            }
        }
        if (list1 == null)
        {
            throw new IllegalArgumentException("first list parameter was null");
        }
        if (list1.isEmpty())
        {
            return false;
        }
        if (list1 == list2)
        {
            return false;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }

        boolean changed = false;
        final ListIterator<T> lit1 = list1.listIterator();
        final ListIterator<T> lit2 = list2.listIterator();
        T obj1 = lit1.next();
        T obj2 = lit2.next();
        while (true)
        {
            final int compareValue = comparator.compare(obj1, obj2);
            if (compareValue < 0)
            {
                lit1.remove();
                changed = true;
                if (lit1.hasNext())
                {
                    obj1 = lit1.next();
                }
                else
                {
                    break;
                }
            }
            else if (compareValue > 0)
            {
                if (lit2.hasNext())
                {
                    obj2 = lit2.next();
                }
                else
                {
                    changed = true;
                    lit1.remove();
                    break;
                }
            }
            else
            {
                if (lit1.hasNext() && lit2.hasNext())
                {
                    obj1 = lit1.next();
                    obj2 = lit2.next();
                }
                else
                {
                    break;
                }
            }
        }
        while (lit1.hasNext())    //true implies that list2 has ended.
        {
            changed = true;
            lit1.next();
            lit1.remove();
        }
        return changed;
    }

    /**
     * Stores the difference of the two sorted lists, list1 and list2, in list1.
     * The resulting list is also sorted. Returns <code>true</code> if list1 is changed.
     * In the simplest case, setDifference performs the "difference" operation from set theory:
     * the final list1 contains a copy of every element that is contained in list1 but not in list2.
     * The general case is more complicated, because the input lists may contain duplicate elements.
     * The generalization is that if a value appears m times in list1 and n times in
     * list2 (where m or n may be zero), then it appears max(m-n,0) times in final list1.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list.
     * @param list2 the second list.
     * @return <code>true</code> if list1 changes.
     */
    public static <T extends Comparable<? super T>> boolean setDifference(final List<T> list1,
            final List<T> list2)
    {
        //TODO fix this
        return setDifference(list1, list2, EQ_COMP);
    }

    /**
     * Stores the difference of the two sorted lists, list1 and list2, in list1
     * using the comparator to compare values. The resulting list is also sorted.
     * Returns <code>true</code> if list1 is changed.
     * In the simplest case, setDifference performs the "difference" operation from set theory:
     * the final list1 contains a copy of every element that is contained in list1 but not in list2.
     * The general case is more complicated, because the input lists may contain duplicate elements.
     * The generalization is that if a value appears m times in list1 and n times in
     * list2 (where m or n may be zero), then it appears max(m-n,0) times in final list1.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list.
     * @param list2 the second list.
     * @param comparator object specifying the comparison logic.
     * @return <code>true</code> if list1 changes.
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> boolean setDifference(final List<T> list1, final List<T> list2,
            final Comparator<? super T> comparator)
    {
        if (list2 == null || list2.isEmpty())
        {
            return false;
        }
        if (list1 == null)
        {
            throw new IllegalArgumentException("first list parameter was null");
        }
        if (list1.isEmpty())
        {
            return false;
        }
        if (list1 == list2)
        {
            list1.clear();
            return true;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }

        boolean changed = false;
        final ListIterator<T> lit1 = list1.listIterator();
        final ListIterator<T> lit2 = list2.listIterator();
        T obj1 = lit1.next();
        T obj2 = lit2.next();
        while (true)
        {
            final int compareValue = comparator.compare(obj1, obj2);
            if (compareValue < 0)
            {
                if (lit1.hasNext())
                {
                    obj1 = lit1.next();
                }
                else
                {
                    break;
                }
            }
            else if (compareValue > 0)
            {
                if (lit2.hasNext())
                {
                    obj2 = lit2.next();
                }
                else
                {
                    break;
                }
            }
            else
            {
                lit1.remove();
                changed = true;
                if ((lit1.hasNext() && lit2.hasNext()))
                {
                    obj1 = lit1.next();
                    obj2 = lit2.next();
                }
                else
                {
                    break;
                }
            }
        }
        return changed;
    }


    /**
     * Stores the symmetric difference of the two sorted lists, list1 and list2, in list1.
     * The resulting list is also sorted. Returns <code>true</code> if list1 is changed.
     * In the simplest case, setSymmetricDifference performs the following operation
     * from set theory: <BR><code> (list1 - list2) U (list2 -list1)</code><BR>
     * That is, the final list1 contains a copy of every element that is contained
     * in list1 but not in list2 and every element in list2 but not in list1.
     * The general case is more complicated, because the input lists may contain duplicate elements.
     * The generalization is that if a value appears m times in list1 and n times in
     * list2 (where m or n may be zero), then it appears abs(m-n) times in final list1.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list.
     * @param list2 the second list.
     * @return <code>true</code> if list1 changes.
     */
    public static <T extends Comparable<? super T>> boolean setSymmetricDifference(final List<T> list1,
            final List<T> list2)
    {
        //TODO fix this
        return setSymmetricDifference(list1, list2, EQ_COMP);
    }

    /**
     * Stores the symmetric difference of the two sorted lists, list1 and list2, in
     * list1 using the comparator to compare values. The resulting list is also sorted.
     * Returns <code>true</code> if list1 is changed.
     * In the simplest case, setSymmetricDifference performs the following operation
     * from set theory: <BR><code> (list1 - list2) U (list2 -list1)</code><BR>
     * That is, the final list1 contains a copy of every element that is contained
     * in list1 but not in list2 and every element in list2 but not in list1.
     * The general case is more complicated, because the input lists may contain duplicate elements.
     * The generalization is that if a value appears m times in list1 and n times in
     * list2 (where m or n may be zero), then it appears abs(m-n) times in final list1.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list.
     * @param list2 the second list.
     * @param comparator object specifying the comparison logic.
     * @return <code>true</code> if list1 changes.
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> boolean setSymmetricDifference(final List<T> list1, final List<T> list2,
            final Comparator<? super T> comparator)
    {
        if (list2 == null || list2.isEmpty())
        {
            return false;
        }
        if (list1 == null)
        {
            throw new IllegalArgumentException("first list parameter was null");
        }
        if (list1 == list2)
        {
            list1.clear();
            return true;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }
        //TODO what happened to random access
        final ListIterator<T> lit1 = list1.listIterator();
        final ListIterator<T> lit2 = list2.listIterator();
        boolean changed = true;
        //let this be done in a generic way as add and delete is being done together
        if (lit1.hasNext() && lit2.hasNext())
        {
            T obj1 = lit1.next();
            T obj2 = lit2.next();
            while (true)
            {
                final int compareValue = comparator.compare(obj1, obj2);
                if (compareValue < 0)
                {
                    if (lit1.hasNext())
                    {
                        obj1 = lit1.next();
                    }
                    else
                    {
                        lit1.add(obj2);
                        break;
                    }
                }
                else if (compareValue > 0)
                {
                    lit1.previous();
                    lit1.add(obj2);
                    lit1.next();
                    changed = true;
                    if (lit2.hasNext())
                    {
                        obj2 = lit2.next();
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    lit1.remove();
                    changed = true;
                    if ((lit1.hasNext() && lit2.hasNext()))
                    {
                        obj1 = lit1.next();
                        obj2 = lit2.next();
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        while (lit2.hasNext())
        {
            lit1.add(lit2.next());
            changed = true;
        }
        return changed;
    }


    /**
     * Merges two sorted lists, list1 and list2, and stores the result into a
     * single sorted list, list1,.
     * That is, it adds elements from list2 into list1 such that the resulting
     * list is also in ascending order.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list
     * @param list2 the second list
     */
    public static <T extends Comparable<? super T>> void merge(final List<T> list1, final List<T> list2)
    {
        //TODO fix this
        merge(list1, list2, EQ_COMP);
    }


    /**
     * Merges two sorted lists, list1 and list2, using the comparator for
     * comparison and stores the result into a single sorted list, list1,.
     * That is, it adds elements from list2 into list1 such that the resulting
     * list is also in ascending order.
     * <BR>
     * <code>null</code> list2 is treated as empty list but passing a <code>null</code>
     * list1 throws an IllegalArgumentException
     * @param list1 the first list
     * @param list2 the second list
     * @param comparator the object containing the comparison logic
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> void merge(final List<T> list1, final List<T> list2,
            final Comparator<? super T> comparator)
    {
        if (list2 == null || list2.isEmpty())
        {
            return;
        }
        if (list1 == null)
        {
            throw new IllegalArgumentException("first list param was null");
        }
        if (list1.isEmpty())
        {
            list1.addAll(list2);
            return;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }


        final ListIterator<T> lit1 = list1.listIterator();
        final ListIterator<T> lit2 = list2.listIterator();
        T obj1 = lit1.next();
        T obj2 = lit2.next();
        while (true)
        {
            final int compareValue = comparator.compare(obj1, obj2);
            if (compareValue > 0)
            {
                lit1.previous();
                lit1.add(obj2);
                lit1.next();
                if (lit2.hasNext())
                {
                    obj2 = lit2.next();
                }
                else
                {
                    break;
                }
            }
            else
            {
                if (lit1.hasNext())
                {
                    obj1 = lit1.next();
                }
                else
                {
                    lit1.add(obj2);
                    break;
                }
            }
        }
        while (lit2.hasNext())    //true implies that list1 has ended
        {
            lit1.add(lit2.next());
        }
    }

    /**
     * Copies elements from inList to outList.
     * <br>Note that this method is slightly different than the Collections.copy(List,List).
     * Here outList can be of any size. outList growes automatically if inList is larger.
     * This is a deviation from STL too.
     * <br>Care must be taken when overlapping lists are used.
     * Say you have a list having the following
     * <br> list {1,2,3,4}
     * <br> Now if you perform the following operation
     * <br><code>ListHelper.copy(list.subList(0,3),list.subList(1,4));</code><br>
     * you will get
     * <br> list {1,1,1,1}
     * <br>
     * <code>null</code> inList is treated the same as an empty list
     * but <code>null</code> outList throws an IllegalArgumentException
     * @param inList the input list
     * @param outList the output list
     */
    public static <T> void copy(final List<T> inList, final List<? super T> outList)
    {
        if (inList == null)
        {
            return;
        }
        if (outList == null)
        {
            throw new IllegalArgumentException("outList was null");
        }

        if (inList instanceof RandomAccess && outList instanceof RandomAccess)
        {
            final int inSize = inList.size();
            final int outSize = outList.size();
            for (int i = 0; i < inSize; i++)
            {
                if (i < outSize)
                {
                    outList.set(i, inList.get(i));
                }
                else
                {
                    outList.add(inList.get(i));
                }
            }
        }
        else
        {
            final ListIterator<T> in = inList.listIterator();
            final ListIterator<? super T> out = outList.listIterator();
            while (in.hasNext())
            {
                if (out.hasNext())
                {
                    out.next();
                    out.set(in.next());
                }
                else
                {
                    out.add(in.next());
                }
            }
        }
    }

    /**
     * Copies the elements of the inList, to the outList except that any element
     * equal to oldValue is not copied; newValue is copied instead.
     * Basically it does copy followed by replace in one go.
     * <br>
     * <code>null</code> inList is treated the same as an empty list
     * but <code>null</code> outList throws an IllegalArgumentException
     * <br>
     * Here outList can be of any size. outList growes automatically if needed.
     * @param inList the input list
     * @param outList the output list
     * @param oldValue the value to be replaced
     * @param newValue the value to be replaced with
     * @see ListHelper#copy(List,List)
     * @see ListHelper#replace(List,Object,Object)
     */
    public static <T, S extends T, R extends T> void replaceCopy(
            final List<T> inList, final List<? super T> outList, final S oldValue, final R newValue)
    {
        if (oldValue == newValue)
        {
            copy(inList, outList);
        }
        else
        {
            replaceCopyIf(inList, outList, new ObjectPredicate(oldValue), newValue);
        }
    }

    /**
     * Copies the elements of the inList, to the outList except that any element
     * which satisfies the predicate is not copied; newValue is copied instead.
     * Basically it does copy followed by replaceIf in one go.
     * <br>
     * <code>null</code> inList is treated the same as an empty list
     * but <code>null</code> outList throws an IllegalArgumentException
     * <br>
     * Here outList can be of any size. outList growes automatically if needed.
     * @param inList the input list
     * @param outList the output list
     * @param predicate the codition for replacement
     * @param newValue the value to be replaced with
     * @see ListHelper#copy(List,List)
     * @see ListHelper#replaceIf(List,Predicate,Object)
     * @throws IllegalArgumentException if passed predicate is null
     */
    public static <T, S extends T> void replaceCopyIf(final List<T> inList, final List<? super T> outList,
            final Predicate<? super T> predicate, final S newValue)
    {
        if (inList == null)
        {
            return;
        }
        if (outList == null)
        {
            throw new IllegalArgumentException("outList was null");
        }
        if (predicate == null)
        {
            throw new IllegalArgumentException("predicate was null");
        }

        if (inList instanceof RandomAccess && outList instanceof RandomAccess)
        {
            final int inSize = inList.size();
            final int outSize = outList.size();
            for (int i = 0; i < inSize; i++)
            {
                final T oVal = inList.get(i);
                final T valueToSet = (predicate.test(oVal)) ? newValue : oVal;
                if (i < outSize)
                {
                    outList.set(i, valueToSet);
                }
                else
                {
                    outList.add(valueToSet);
                }
            }
        }
        else
        {
            final ListIterator<T> in = inList.listIterator();
            final ListIterator<? super T> out = outList.listIterator();
            while (in.hasNext())
            {
                final T oVal = in.next();
                final T valueToSet = (predicate.test(oVal)) ? newValue : oVal;
                if (out.hasNext())
                {
                    out.next();
                    out.set(valueToSet);
                }
                else
                {
                    out.add(valueToSet);
                }
            }
        }
    }


    /**
     * Copies the elements of the inList that are not equal to value, to the outList.
     * Similar to copy followed by remove in one go.
     * <br>
     * <code>null</code> inList is treated the same as an empty list
     * but <code>null</code> outList throws an IllegalArgumentException
     * <br>
     * Here outList can be of any size. outList growes automatically if needed.
     * @param inList the input list
     * @param outList the output list
     * @param value the value to be removed
     * @see ListHelper#copy(List,List)
     * @see ListHelper#remove(List,Object)
     */
    public static <T, S extends T> void removeCopy(final List<T> inList,
            final List<? super T> outList, final S value)
    {
        removeCopyIf(inList, outList, new ObjectPredicate(value));
    }

    /**
     * Copies the elements of the inList that do not satify the predicate, to the outList.
     * Similar copy followed by removeIf in one go.
     * <br>
     * <code>null</code> inList is treated the same as an empty list
     * but <code>null</code> outList throws an IllegalArgumentException
     * <br>
     * Here outList can be of any size. outList growes automatically if needed.
     * @param inList the input list
     * @param outList the output list
     * @param predicate the codition for removal
     * @see ListHelper#copy(List,List)
     * @see ListHelper#removeIf(List,Predicate)
     * @throws IllegalArgumentException if passed predicate is null
     */
    public static <T> void removeCopyIf(final List<T> inList, final List<? super T> outList,
            final Predicate<? super T> predicate)
    {
        if (inList == null)
        {
            return;
        }
        if (outList == null)
        {
            throw new IllegalArgumentException("outList was null");
        }
        if (predicate == null)
        {
            throw new IllegalArgumentException("predicate was null");
        }

        if (inList instanceof RandomAccess && outList instanceof RandomAccess)
        {
            final int inSize = inList.size();
            final int outSize = outList.size();
            T oVal;
            int outIndex = 0;
            for (int i = 0; i < inSize; i++)
            {
                oVal = inList.get(i);
                if (!predicate.test(oVal))
                {
                    if (outIndex < outSize)
                    {
                        outList.set(outIndex++, oVal);
                    }
                    else
                    {
                        outList.add(oVal);
                    }
                }
            }
        }
        else
        {
            final ListIterator<T> in = inList.listIterator();
            final ListIterator<? super T> out = outList.listIterator();
            T oVal;
            while (in.hasNext())
            {
                oVal = in.next();
                if (!predicate.test(oVal))
                {
                    if (out.hasNext())
                    {
                        out.next();
                        out.set(oVal);
                    }
                    else
                    {
                        out.add(oVal);
                    }
                }
            }
        }
    }


    /**
     * Copies elements from inList to the outList, except that in a consecutive
     * group of duplicate elements only the first one is copied.
     * Similar to copy followed by unique in one go.
     * <br>
     * <code>null</code> inList is treated the same as an empty list
     * but <code>null</code> outList throws an IllegalArgumentException
     * <br>
     * Here outList can be of any size. outList growes automatically if needed.
     * @param inList the input list
     * @param outList the output list
     * @see ListHelper#copy(List,List)
     * @see ListHelper#unique(List)
     */
    public static <T> void uniqueCopy(final List<T> inList, final List<? super T> outList)
    {
        uniqueCopy(inList, outList, EQ_BIN_PRED);
    }

    /**
     * Copies elements from inList to the outList, except that in a consecutive
     * group of duplicate elements only the first one is copied.
     * Instead of using the normal equals method to compare, it uses the binary predicate.
     * Similar to copy followed by unique in one go.
     * <br>
     * <code>null</code> inList is treated the same as an empty list
     * but <code>null</code> outList throws an IllegalArgumentException
     * <br>
     * Here outList can be of any size. outList growes automatically if needed.
     * @param inList the input list
     * @param outList the output list
     * @param binaryPredicate the condtion to check for equality
     * @see ListHelper#copy(List,List)
     * @see ListHelper#unique(List,BinaryPredicate)
     * @throws IllegalArgumentException if passed binaryPredicate is null
     */
    public static <T> void uniqueCopy(final List<T> inList, final List<? super T> outList,
            final BinaryPredicate<? super T> binaryPredicate)
    {
        if (inList == null)
        {
            return;
        }
        if (binaryPredicate == null)
        {
            throw new IllegalArgumentException("BinaryPredicate was null");
        }
        if (outList == null)
        {
            throw new IllegalArgumentException("outList was null");
        }

        if (inList instanceof RandomAccess && outList instanceof RandomAccess)
        {
            final int inSize = inList.size();
            final int outSize = outList.size();
            int inIndex = 0;
            int outIndex = 0;
            T value = inList.get(inIndex++);
            if (outIndex < outSize)
            {
                outList.set(outIndex++, value);
            }
            else
            {
                outList.add(value);
            }
            T next;
            while (inIndex < inSize)
            {
                next = inList.get(inIndex++);
                if (!binaryPredicate.test(value, next))
                {
                    value = next;
                    if (outIndex < outSize)
                    {
                        outList.set(outIndex++, value);
                    }
                    else
                    {
                        outList.add(value);
                    }
                }
            }
        }
        else
        {
            final ListIterator<T> in = inList.listIterator();
            final ListIterator<? super T> out = outList.listIterator();
            T value = in.next();
            if (out.hasNext())
            {
                out.next();
                out.set(value);
            }
            else
            {
                out.add(value);
            }
            T next;
            while (in.hasNext())
            {
                next = in.next();
                if (!binaryPredicate.test(value, next))
                {
                    value = next;
                    if (out.hasNext())
                    {
                        out.next();
                        out.set(value);
                    }
                    else
                    {
                        out.add(value);
                    }
                }
            }
        }
    }


    /**
     * Reverses the elements of the list.
     * <code>null</code> list are treated as empty list.
     * @param list the list to reverse
     */
    public static <T> void reverse(final List<T> list)
    {
        if (list == null)
        {
            return;
        }
        final int size = list.size();
        if (list instanceof RandomAccess)
        {
            for (int i = 0, mid = size >> 1, j = size - 1; i < mid; i++, j--)
            {
                list.set(i, list.set(j, list.get(i)));
            }
        }
        else
        {
            final ListIterator<T> fwd = list.listIterator();
            final ListIterator<T> rev = list.listIterator(size);
            for (int i = 0, mid = size >> 1; i < mid; i++)
            {
                final T tmp = fwd.next();
                fwd.set(rev.previous());
                rev.set(tmp);
            }
        }
    }

    /**
     * Copies the elements from the first list into the second list, reversing the
     * order of the elements. Same as copy followed by reverse in one go.
     * <br>
     * <code>null</code> inList is treated the same as an empty list
     * but <code>null</code> outList throws an IllegalArgumentException
     * <br>
     * Here outList can be of any size. outList growes automatically if needed.
     * @param inList the input list
     * @param outList the output list
     * @see ListHelper#copy(List,List)
     */
    public static <T> void reverseCopy(final List<T> inList, final List<? super T> outList)
    {
        if (inList == null)
        {
            return;
        }
        if (outList == null)
        {
            throw new IllegalArgumentException("outList was null");
        }

        if (inList instanceof RandomAccess && outList instanceof RandomAccess)
        {
            final int outSize = outList.size();
            int inIndex = inList.size() - 1;
            int outIndex = 0;
            while (inIndex >= 0)
            {
                if (outIndex < outSize)
                {
                    outList.set(outIndex++, inList.get(inIndex--));
                }
                else
                {
                    outList.add(inList.get(inIndex--));
                }
            }
        }
        else
        {
            final ListIterator<T> in = inList.listIterator(inList.size());
            final ListIterator<? super T> out = outList.listIterator();
            while (in.hasPrevious())
            {
                if (out.hasNext())
                {
                    out.next();
                    out.set(in.previous());
                }
                else
                {
                    out.add(in.previous());
                }
            }
        }
    }

    /**
     * Compares the two lists, list1 and list2, lexicographically and returns 0
     * if they are equivalent, -ve number when list1 would appear first in
     * dictionary order, +ve number otherwise. <BR>
     * Lexicographical comparison means "dictionary" (element-by-element) ordering.
     * That is, list1 is less than list2 if list1[0] is less than list2[0], and
     * greater if list1[0] is greater than list2[0].
     * If the two first elements are equivalent then lexicographicalCompare
     * compares the two second elements, and so on.
     * As with ordinary dictionary order, list1 is considered to be less than list2
     * if every element in list1 is equal to the corresponding element in list2
     * but the second contains more elements.<br>
     * The numerical value of the returned values is one more than the index that differed.
     * Say the ith element of the first list was smaller than the ith element of the second list
     * and other elements before before this index were same in both the lists
     * then the returned value will be -(i+1)
     * If the list1 has the same elements as list2 and in the same order but is longer
     * then the returned value will be (list1.size()+1).<br>
     * <code>null</code> lists are considered same as empty lists
     * @param list1 the first list
     * @param list2 the second list
     * @return 0 if the lists are equivalent, -ve number when list1 would appear
     *         first in dictionary order, +ve number otherwise.
     */
    public static <T extends Comparable<? super T>> int lexicographicalCompare(
            final List<T> list1, final List<T> list2)
    {
        return lexicographicalCompare(list1, list2, EQ_COMP);
    }

    /**
     * Compares the two lists, list1 and list2, lexicographically and returns 0
     * if they are equivalent, -ve number when list1 would appear first in
     * dictionary order, +ve number otherwise. Uses comparator for comparison. <br>
     * Lexicographical comparison means "dictionary" (element-by-element) ordering.
     * That is, list1 is less than list2 if list1[0] is less than list2[0], and
     * greater if list1[0] is greater than list2[0].
     * If the two first elements are equivalent then lexicographicalCompare
     * compares the two second elements, and so on.
     * As with ordinary dictionary order, list1 is considered to be less than list2
     * if every element in list1 is equal to the corresponding element in list2
     * but the second contains more elements.<br>
     * The numerical value of the returned values is one more than the index that differed.
     * Say the ith element of the first list was smaller than the ith element of the second list
     * and other elements before before this index were same in both the lists
     * then the returned value will be -(i+1)
     * If the list1 has the same elements as list2 and in the same order but is longer
     * then the returned value will be (list1.size()+1).<br>
     * <code>null</code> lists are considered same as empty lists
     * @param list1 the first list
     * @param list2 the second list
     * @param comparator the object containing the comparison logic
     * @return 0 if the lists are equivalent, -ve number when list1 would appear
     *         first in dictionary order, +ve number otherwise.
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> int lexicographicalCompare(final List<T> list1,
            final List<T> list2, final Comparator<? super T> comparator)
    {
        if (list1 == null)
        {
            return (list2 == null || list2.isEmpty()) ? 0 : -1;
        }
        if (list2 == null)
        {
            return (list1.isEmpty()) ? 0 : 1;
        }
        if (list1 == list2)
        {
            return 0;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }

        if (list1 instanceof RandomAccess && list2 instanceof RandomAccess)
        {
            final int size1 = list1.size();
            final int size2 = list2.size();
            int index1 = 0;
            int index2 = 0;
            int count = 0;
            while (index1 < size1 && index2 < size2)
            {
                ++count;
                final int compareValue = comparator.compare(list1.get(index1++), list2.get(index2++));
                if (compareValue < 0)
                {
                    return -1 * count;
                }
                else if (compareValue > 0)
                {
                    return count;
                }
            }
            ++count;
            return (index2 >= size2) ? ((index1 >= size1) ? 0 : count) : -1 * count;
        }
        else
        {
            final ListIterator<? extends T> lit1 = list1.listIterator();
            final ListIterator<? extends T> lit2 = list2.listIterator();
            int count = 0;
            while (lit1.hasNext() && lit2.hasNext())
            {
                ++count;
                final int compareVal = comparator.compare(lit1.next(), lit2.next());
                if (compareVal < 0)
                {
                    return -1 * count;
                }
                else if (compareVal > 0)
                {
                    return count;
                }
            }
            ++count;
            return (!lit2.hasNext()) ? ((!lit1.hasNext()) ? 0 : count) : -1 * count;
        }
    }


    /**
     * Sorts the list. Uses <code>Collections.sort(List)</code>.
     * Included here for completeness
     * @param list list to be sorted
     */
    public static <T extends Comparable<? super T>> void sort(final List<T> list)
    {
        Collections.sort(list, EQ_COMP);
    }

    /**
     * Sorts the list using the given comparator.
     * Uses <code>Collections.sort(List,Comparator)</code>.
     * Included here for completeness
     * @param list list to be sorted
     * @param comparator comparator to be used
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> void sort(final List<T> list, final Comparator<? super T> comparator)
    {
        if (list == null)
        {
            return;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }
        Collections.sort(list, comparator);
    }


    /**
     * Returns <code>true</code> if the list represents a heap, and <code>false</code> otherwise.
     * @param list list
     * @return <code>true</code> if the list represents a heap, and <code>false</code> otherwise.
     */
    public static <T extends Comparable<? super T>> boolean isHeap(final List<T> list)
    {
        return isHeap(list, EQ_COMP);
    }

    /**
     * Returns <code>true</code> if the list represents a heap when using the
     * comparator to compare the objects, and <code>false</code> otherwise.
     * @param list list
     * @param comparator comparator
     * @return <code>true</code> if the list represents a heap when using the
     *         comparator to compare the objects, and <code>false</code> otherwise.
     * @throws IllegalArgumentException if passed comparator is null
     */
    public static <T> boolean isHeap(final List<T> list, final Comparator<? super T> comparator)
    {
        if (list == null)
        {
            return true;
        }
        if (comparator == null)
        {
            throw new IllegalArgumentException("Comparator was null");
        }

        int parent = 0;
        final int n = list.size();
        T parentObj = list.get(parent);
        for (int child = 1; child < n; ++child)
        {
            if (comparator.compare(parentObj, list.get(child)) < 0)
            {
                return false;
            }
            if ((child & 1) == 0)
            {
                ++parent;
                parentObj = list.get(parent);
            }
        }
        return true;
    }


    private static final class EqBinPred implements BinaryPredicate<Object>
    {
        public boolean test(final Object obj1, final Object obj2)
        {
            return (obj1 == null ? obj2 == null : obj1.equals(obj2));
        }
    }

    private static final class NullLowComparator implements Comparator<Object>
    {
        public int compare(final Object obj1, final Object obj2)
        {
            if (obj1 == null)
            {
                return (obj2 == null) ? 0 : -1;
            }
            else
            {
                return (obj2 == null) ? 1 : ((Comparable) obj1).compareTo(obj2);
            }
        }
    }

    private static final class ObjectPredicate implements Predicate<Object>
    {
        final Object object;

        ObjectPredicate(final Object obj)
        {
            object = obj;
        }

        public boolean test(final Object obj)
        {
            return ((object == null) ? (obj == null) : object.equals(obj));
        }
    }

    private static final BinaryPredicate<Object> EQ_BIN_PRED = new EqBinPred();

    private static final Comparator<Object> EQ_COMP = new NullLowComparator();

}
